package common.sort;

import java.util.Arrays;

/**
 * 原理:
 * 1. 分成若干个小数组
 * 2. 依次两两合并，并有序
 * 3. 重复第二步
 */
public class MergeSort implements Sort {

    @Override
    public void sort(int[] array) {
        final int[] sortArr = sortMerge(array);
        System.arraycopy(sortArr, 0, array, 0, array.length);
    }

    private int[] sortMerge(int[] array) {
        int LEN = array.length;

        if (LEN <= 1) {
            return array;
        }

        int middle = LEN >> 1;
        int[] leftArr = Arrays.copyOfRange(array, 0, middle);
        int[] rightArr = Arrays.copyOfRange(array, middle, LEN);
        return merge(sortMerge(leftArr), sortMerge(rightArr));
    }

    private int[] merge(int[] leftArr, int[] rightArr) {
        int[] allArr = new int[leftArr.length + rightArr.length];
        int leftIndex = 0, rightIndex = 0, idx = 0;
        while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
            if (leftArr[leftIndex] < rightArr[rightIndex]) {
                allArr[idx++] = leftArr[leftIndex++];
            } else {
                allArr[idx++] = rightArr[rightIndex++];
            }
        }

        while (leftIndex < leftArr.length) {
            allArr[idx++] = leftArr[leftIndex++];
        }
        while (rightIndex < rightArr.length) {
            allArr[idx++] = rightArr[rightIndex++];
        }
        return allArr;
    }
}
